---
title: "奇迹"
created: 2025-11-28
tags:
  - 算法
---

# 奇迹

## 题目 [奇迹](https://www.luogu.com.cn/problem/P5440)

![[image-757c5ab9.png]]

## 思路分析

![[image-da5054df.png]]

非常好的题目 虽然有几个tle 但是没关系 锻炼dfs思路

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leap(int y){

	return (y%4==0 && y%100!=0) || (y%400==0);

}

int get_days(int y,int m){

	return days[m]+(m==2 && is_leap(y));

}

void next_day(int &y,int &m,int &d){

	d++;

	if(d>get_days(y,m)){

		d=1;

		m++;

		if(m>12){

			m=1;

			y++;

		}

	}

}

bool check_date(int y,int m,int d){

	if(y<1 || y>9999)	return false;

	if(d<1 || d>get_days(y,m))	return false;

	if(m<1 || m>12)	return false;

	return true;

}

bool is_prime(int n){

	if(n<2)	return false;

	for(int i=2;i<=n/i;i++){

		if(n%i==0){

			return false;

		}

	}

	return true;

}

int ans=0;

void dfs(string &s,int pos){

	if(pos==8){

		int year=stoi(s.substr(0,4));

		int month=stoi(s.substr(4,2));

		int day=stoi(s.substr(6,2));

		if(!check_date(year,month,day))		return;

		int day2=stoi(s.substr(6,2));

		int md4=stoi(s.substr(4,4));

		int ymd8=stoi(s);

		if(is_prime(day2) && is_prime(md4) && is_prime(ymd8)){

			ans++;

		}

		return;

	}

	if(s[pos]!='-'){

		dfs(s,pos+1);

	}else{

		for(char c='0';c<='9';c++){

			s[pos]=c;

			dfs(s,pos+1);

			s[pos]='-';

		}

	}

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int T;cin>>T;

	while(T--){

		string s;cin>>s;

		ans=0;

		dfs(s,0);

		cout<<ans<<endl;

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[Scales S|Scales S]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/指数型（每个位置都可以选所有情况）/6、七段码|6、七段码]]